﻿//一、定长滑动窗口
//§1.1 基础
//【套路】教你解决定长滑窗！适用于所有定长滑窗题目！
//
//1456. 定长子串中元音的最大数目 1263
//643. 子数组最大平均数 I
//1343. 大小为 K 且平均值大于等于阈值的子数组数目 1317
//2090. 半径为 k 的子数组平均值 1358
//2379. 得到 K 个黑块的最少涂色次数 1360
//1652. 拆炸弹 1417
//1052. 爱生气的书店老板 1418
//2841. 几乎唯一子数组的最大和 1546
//2461. 长度为 K 子数组中的最大和 1553
//1423. 可获得的最大点数 1574
//1297. 子串的最大出现次数 1748
//2653. 滑动子数组的美丽值 1786
//1176. 健身计划评估（会员题）
//1100. 长度为 K 的无重复字符子串（会员题）
//1852. 每个子数组的数字种类数（会员题）
//1151. 最少交换次数来组合所有的 1（会员题）
//2107. 分享 K 个糖果后独特口味的数量（会员题）
//§1.2 进阶（选做）
//2134. 最少交换次数来组合所有的 1 II 1748
//1888. 使二进制字符串字符交替的最少反转次数 2006
//567. 字符串的排列
//438. 找到字符串中所有字母异位词
//30. 串联所有单词的子串
//2156. 查找给定哈希值的子串 2063
//2953. 统计完全子字符串 2449
//683. K 个关闭的灯泡（会员题）做到o(n)
//2067. 等计数子串的数量（会员题）
//2524. 子数组的最大频率分数（会员题）
//§1.3 其他（选做）
//2269. 找到一个数字的 K 美丽值 1280
//1984. 学生分数的最小差值 1306
//220. 存在重复元素 III
//
//二、不定长滑动窗口
//不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组个数。
//
//推荐先完成 2000 分以下的题目，难题可以留到后面再做。
//
//§2.1 求最长 / 最大
//3. 无重复字符的最长子串
//3090. 每个字符最多出现两次的最长子字符串 1329
//1493. 删掉一个元素以后全为 1 的最长子数组 1423
//1208. 尽可能使字符串相等 1497
//2730. 找到最长的半重复子字符串 1502
//904. 水果成篮 1516
//1695. 删除子数组的最大得分 1529
//2958. 最多 K 个重复元素的最长子数组 1535
//2779. 数组的最大美丽值 1638
//2024. 考试的最大困扰度 1643
//1004. 最大连续 1 的个数 III 1656
//1658. 将 x 减到 0 的最小操作数 1817
//1838. 最高频元素的频数 1876
//2516. 每种字符至少取 K 个 1948
//2831. 找出最长等值子数组 1976
//2271. 毯子覆盖的最多白色砖块数 2022
//2106. 摘水果 2062
//2555. 两个线段获得的最多奖品 2081
//2009. 使数组连续的最少操作数 2084
//1610. 可见点的最大数目 2147
//2781. 最长合法子字符串的长度 2204
//2968. 执行操作使频率分数最大 2444
//1040. 移动石子直到连续 II 2456
//395. 至少有 K 个重复字符的最长子串
//1763. 最长的美好子字符串 非暴力做法
//487. 最大连续 1 的个数 II（会员题）
//159. 至多包含两个不同字符的最长子串（会员题）
//340. 至多包含 K 个不同字符的最长子串（会员题）
//
//§2.2 求最短 / 最小
//209. 长度最小的子数组
//2904. 最短且字典序最小的美丽子字符串 做到O(n^2)
//1234. 替换子串得到平衡字符串 1878
//2875. 无限数组的最短子数组 1914
//1574. 删除最短的子数组使剩余数组有序 1932
//76. 最小覆盖子串
//632. 最小区间
//727. 最小窗口子序列（会员题）联系 76 题
//§2.3 求子数组个数
//713. 乘积小于 K 的子数组
//1358. 包含所有三种字符的子字符串数目 1646
//2962. 统计最大元素出现至少 K 次的子数组 1701
//3258. 统计满足 K 约束的子字符串数量 I 做到O(n)
//2799. 统计完全子数组的数目 做到O(n)
//2302. 统计得分小于 K 的子数组数目 1808
//2537. 统计好子数组的数目 1892
//2762. 不间断子数组 1940
//3134. 找出唯一性数组的中位数 2451
//3261. 统计满足 K 约束的子字符串数量 II 2659
//LCP 68. 美观的花束
//2743. 计算没有重复字符的子字符串数量（会员题）
//§2.4 其他（选做）
//1438. 绝对差不超过限制的最长连续子数组 1672
//2401. 最长优雅子数组 1750
//1156. 单字符重复子串的最大长度 1787 有简单做法
//424. 替换后的最长重复字符
//1918. 第 K 小的子数组和（会员题)
//
//三、单序列双指针
//§3.1 相向双指针
//两个指针
//left = 0, right = n−1，从数组的两端开始，向中间移动。上面的滑动窗口相当于同向双指针。
//
//125. 验证回文串
//1750. 删除字符串两端相同字符后的最短长度 1502
//2105. 给植物浇水 II 1507
//977. 有序数组的平方 做到O(n)
//658. 找到 K 个最接近的元素
//1471. 数组中的 K 个最强值 用双指针解决
//167. 两数之和 II - 输入有序数组
//2824. 统计和小于目标的下标对数目
//LCP 28. 采购方案 同 2824 题
//15. 三数之和
//16. 最接近的三数之和
//18. 四数之和
//611. 有效三角形的个数
//1577. 数的平方等于两数乘积的方法数 用双指针实现
//923. 三数之和的多种可能 1711
//948. 令牌放置 1762
//11. 盛最多水的容器
//42. 接雨水
//1616. 分割两个字符串得到回文串 1868
//1498. 满足条件的子序列数目 2276
//1782. 统计点对的数目 2457
//1099. 小于 K 的两数之和（会员题）
//360. 有序转化数组（会员题）
//2422. 使用合并操作将数组转换为回文序列（会员题）
//259. 较小的三数之和（会员题）
//§3.2 同向双指针
//两个指针的移动方向相同（都向右，或者都向左）。
//
//1346. 检查整数及其两倍数是否存在
//532. 数组中的 k - diff 数对
//2122. 还原原数组 2159
//§3.3 背向双指针
//两个指针从数组中的同一个位置出发，一个向左，另一个向右，背向移动。
//
//1793. 好子数组的最大分数 1946
//§3.4 移除子数组
//581. 最短无序连续子数组
//2972. 统计移除递增子数组的数目 II 2153
//2565. 最少得分子序列 2432
//§3.5 原地修改
//27. 移除元素
//26. 删除有序数组中的重复项
//80. 删除有序数组中的重复项 II
//283. 移动零
//905. 按奇偶排序数组
//922. 按奇偶排序数组 II
//2460. 对数组执行操作
//1089. 复写零
//
//四、双序列双指针
//§4.1 双指针
//2540. 最小公共值 做到O(n + m)
//88. 合并两个有序数组 做到O(n + m)
//2570. 合并两个二维数组 - 求和法 做到O(n + m)
//LCP 18. 早餐组合
//1385. 两个数组间的距离值
//1855. 下标对中的最大距离 1515
//925. 长按键入 做到O(n + m)
//809. 情感丰富的文字 1605
//2337. 移动片段得到字符串 1693
//777. 在 LR 字符串中交换相邻字符 同 2337 题
//844. 比较含退格的字符串 做到O(1) 额外空间
//986. 区间列表的交集 做到O(n + m)
//2070. 每一个查询的最大美丽值 1724
//面试题 16.06.最小差
//1537. 最大得分 1961
//244. 最短单词距离 II（会员题）
//2838. 英雄可以获得的最大金币数（会员题）
//1229. 安排会议日程（会员题）
//1570. 两个稀疏向量的点积（会员题）
//1868. 两个行程编码数组的积（会员题）
//§4.2 判断子序列
//392. 判断子序列
//524. 通过删除字母匹配到字典里最长单词
//2486. 追加字符以获得子序列 1363
//2825. 循环增长使字符串子序列等于另一个字符串 1415
//1023. 驼峰式匹配 1537
//3132. 找出与数组相加的整数 II 1620
//522. 最长特殊序列 II ~1700
//1898. 可移除字符的最大数目 1913
//1055. 形成字符串的最短路径（会员题）
//五、三指针
//§5.1 滑动窗口
//
//930. 和相同的二元子数组 1592
//1248. 统计「优美子数组」 1624
//1712. 将数组分成三个子数组的方案数 2079
//992. K 个不同整数的子数组 2210
//1989. 捉迷藏中可捕获的最大人数（会员题）
//§5.2 非滑动窗口
//2367. 等差三元组的数目 做到
//O(n)
//825. 适龄的朋友 1697
//2563. 统计公平数对的数目 1721
//795. 区间子数组个数 1817
//2444. 统计定界子数组的数目 2093
//1213. 三个有序数组的交集（会员题）


//1652拆炸弹
//你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。
//
//为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。
//
//如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
//如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
//	如果 k == 0 ，将第 i 个数字用 0 替换。
//	由于 code 是循环的， code[n - 1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n - 1] 。
//
//	给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

#include<bits/stdc++.h>
using namespace std;
#include<string>
#include<vector>


//class Solution
//{
//public:
//    vector<int> decrypt(vector<int>& code, int k)
//    {
//        int n = code.size(), sum = 0;
//        vector<int>ret(n, 0);
//        if (k == 0)
//        {
//            return ret;
//        }
//        else if (k > 0)
//        {
//            int left = 1, right = k + 1;
//            for (int i = 1; i <= k; ++i)
//            {
//                sum += code[i % n];
//            }
//            for (int i = 0; i < n; ++i)
//            {
//                ret[i] = sum;
//                sum += code[(i + 1 + k) % n];
//                sum -= code[(i + 1) % n];
//            }
//        }
//        else
//        {
//            k = -k;
//            for (int i = 0; i < k; ++i)
//            {
//                sum += code[i % n];
//            }
//
//            for (int i = 0; i < n; ++i)
//            {
//                ret[(i + k) % n] = sum;
//                sum += code[(i + k) % n];//一定要注意通过取模来实现带环的效果
//                sum -= code[(i) % n];
//            }
//        }
//        return ret;
//    }
//};

//有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。
//
//在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
//
//当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
//
//书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
//
//请你返回 这一天营业下来，最多有多少客户能够感到满意 。

//1052爱生气的书店老板
//class Solution
//{
//public:
//    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int k)
//    {
//        int n = customers.size();
//        int sum = 0, Max = 0, num = 0;
//        int left = 0, right = 0;
//        for (int i = 0; i < n; ++i)
//        {
//            if (grumpy[i] == 0)
//            {
//                sum += customers[i];
//            }
//        }
//        //先算出初识的满意的顾客
//
//        Max = sum;
//        for (int i = 0; i < k; ++i)
//        {
//            if (grumpy[i] == 1)
//            {
//                sum += customers[i];
//            }
//        }
//        //以k为定长，进行滑动窗口
//        for (int i = 0; i <= n - k; ++i)
//        {
//            if (Max < sum)
//            {
//                Max = sum;
//            }
//
//            if (i + k == n)
//            {
//                return Max;
//            }
//            if (grumpy[i + k] == 1)
//            {
//                sum += customers[i + k];
//            }
//            if (grumpy[i] == 1)
//            {
//                sum -= customers[i];
//            }
//        }
//        return Max;
//    }
//};

//2841几乎唯一子数组的最大和

//给你一个整数数组 nums 和两个正整数 m 和 k 。
//
//请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
//
//如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
//
//子数组指的是一个数组中一段连续 非空 的元素序列。

#include<unordered_map>
//class Solution
//{
//public:
//    typedef long long ll;
//    long long maxSum(vector<int>& nums, int m, int k)
//    {
//        unordered_map<int, int> hash;
//        ll Max = 0, sum = 0;
//
//        // 处理边界情况
//        if (nums.size() < k)
//        {
//            return 0;
//        }
//
//        // 初始化滑动窗口
//        for (ll i = 0; i < k; ++i)
//        {
//            sum += nums[i];
//            hash[nums[i]]++;
//        }
//
//        // 检查初始窗口是否满足条件
//        if (hash.size() >= m)
//        {
//            Max = sum;
//        }
//
//        // 开始滑动窗口
//        for (ll left = 0, right = k; right < nums.size();)
//        {
//            sum += nums[right];
//            sum -= nums[left];
//
//            hash[nums[right]]++;
//            hash[nums[left]]--;
//            if (hash[nums[left]] == 0)
//            {
//                hash.erase(nums[left]);
//            }
//
//            left++;
//            right++;
//
//            // 如果当前窗口内的不同元素数 >= m，则更新最大和
//            if (hash.size() >= m)
//            {
//                Max = max(Max, sum);
//            }
//        }
//
//        return Max;
//    }
//};

//2461 长度为k子数组中的最大和
//给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
//
//子数组的长度是 k，且
//子数组中的所有元素 各不相同 。
//返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
//
//子数组 是数组中一段连续非空的元素序列。

//class Solution 
//{
//public:
//    typedef long long ll;
//    long long maximumSubarraySum(vector<int>& nums, int k) 
//    {
//        ll sum = 0;
//        ll ret = 0;
//
//        ll n = nums.size();
//        unordered_map<int, int>hash;//要求不重复，用hash来检测是否出现重复字符
//        bool flag = true;
//        for (int i = 0; i < k; ++i)
//        {
//            sum += nums[i];
//            hash[nums[i]]++;
//            if (hash[nums[i]] > 1)
//            {
//                flag = false;
//            }
//        }
//        if ( flag)
//        {
//            ret = sum;
//        }
//
//        for (ll left = 0, right = k; right < n;right++,left++)
//        {
//            sum += nums[right];
//            sum -= nums[left];
//
//            hash[nums[right]]++;
//            hash[nums[left]]--;
//            if (hash[nums[left]] == 0)
//            {
//                hash.erase(nums[left]);
//            }
//            if (hash[nums[right]] > 1)
//            {
//                continue;
//            }
//            if (hash.size() != k)//hash的大小等于k时说没有重复，可以进行下一步的判断更新ret的步骤
//            {
//                continue;
//            }
//            if (ret < sum)
//            {
//                ret = sum;
//            }
//        }
//        return ret;
//    }
//};

//1423可获得的最大点数

//几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
//
//每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
//
//你的点数就是你拿到手中的所有卡牌的点数之和。
//
//给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

//class Solution
//{
//public:
//    typedef long long ll;
//    int maxScore(vector<int>& cardPoints, int k)
//    {
//        ll sum = 0;
//        for (auto& it : cardPoints)
//        {
//            sum += it;
//        }
//
//        ll num = 0, n = cardPoints.size() - k;
//        for (int i = 0; i < n; ++i)
//        {
//            num += cardPoints[i];
//        }
//
//        ll Min = INT_MAX;
//        if (num < Min)
//        {
//            Min = num;
//        }
//
//        for (int left = 0, right = n; right < cardPoints.size(); ++right, ++left)
//        {
//            num += cardPoints[right];
//            num -= cardPoints[left];
//
//            if (num < Min)
//            {
//                Min = num;
//            }
//        }
//
//        return sum - Min;
//    }
//};


//1297子串出现的最大次数
//
//给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
//
//子串中不同字母的数目必须小于等于 maxLetters 。
//子串的长度必须大于等于 minSize 且小于等于 maxSize 。

//class Solution //实际上也是一个定长的滑动窗口，只需要管最小长度的字符串就行
//{
//public:
//    int maxFreq(string s, int maxLetters, int minSize, int maxSize) 
//    {
//        //注意思维，maxSize没啥用，长的字符串满足那么他的子字符串也一定重复次数大于等于它
//        unordered_map<string, int>hash1;
//        unordered_map<char, int>hash2;
//
//        string ss, ret;
//        int Max = 0;
//
//        for (int i = 0; i < minSize; ++i)
//        {
//            ss += s[i];
//            hash2[s[i]]++;
//        }
//        hash1[ss]++;
//        if (hash2.size() > maxLetters)
//        {
//            Max = 0;
//        }
//        else
//        {
//            Max = 1;
//        }
//
//        for (int left = 0, right = minSize; right < s.size(); left++, right++)
//        {
//            ss.erase(0, 1);
//            ss += s[right];
//
//            hash2[s[left]]--;
//            if (hash2[s[left]] == 0)
//            {
//                hash2.erase(s[left]);
//            }
//            hash2[s[right]]++;
//
//            hash1[ss]++;
//
//            if (hash2.size() > maxLetters)
//            {
//                continue;
//            }
//
//            if (hash1[ss] > Max)
//            {
//                Max = hash1[ss];
//            }
//        }
//        return Max;
//    }
//};

//2653 滑动子数组的美丽值

//给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。
//
//一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
//
//请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。
//
//子数组指的是数组中一段连续 非空 的元素序列。
#include<set>
#include<iterator>

//class Solution
//{
//public:
//    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x)
//    {
//        multiset<int> small;   // 保存前x小的元素
//        multiset<int> large;   // 保存剩余的元素
//        vector<int> ret;
//
//        // 初始化窗口
//        for (int i = 0; i < k; ++i)
//        {
//            small.insert(nums[i]);
//            if (small.size() > x)
//            {
//                large.insert(*small.rbegin());//当插入元素大于x个，就把第small最大的插入large，
//                small.erase(prev(small.end()));//prev返回给定迭代器的前一个位置，也就是返回最大值
//                //这里不使用rbegin是因为rbegin是反向迭代器，不支持erase的操作
//            }
//        }
//
//        // 获取当前的x小元素
//        auto getNumX = [&small]() -> int
//            {
//                return *small.rbegin();  // 返回small中的最大值，即第x小元素
//            };
//
//        // 计算初始窗口的美丽值
//        int num = getNumX();
//        ret.push_back(num < 0 ? num : 0);
//
//        // 滑动窗口
//        for (int left = 0, right = k; right < nums.size(); ++left, ++right)
//        {
//            // 插入新元素
//            if (nums[right] <= *small.rbegin())//小于的话就要插入到small里，并且让small的最大值插入到large里
//            {
//                small.insert(nums[right]);
//                if (small.size() > x)
//                {
//                    large.insert(*small.rbegin());
//                    small.erase(prev(small.end()));
//                }
//            }
//            else
//            {
//                large.insert(nums[right]);//大于直接插入到large
//            }
//
//            // 删除旧元素
//            if (nums[left] <= *small.rbegin())
//            {
//                small.erase(small.find(nums[left]));
//                small.insert(*large.begin());
//                large.erase(large.begin());           
//            }
//            else
//            {
//                large.erase(large.find(nums[left]));
//            }
//
//            // 计算当前窗口的美丽值
//            num = getNumX();
//            ret.push_back(num < 0 ? num : 0);
//        }
//
//        return ret;
//    }
//};


//
//2134. 最少交换次数来组合所有的 1 II
//
//交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
//
//环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
//
//给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

class Solution
{
public:
    int minSwaps(vector<int>& nums) 
    {
        int num = 0;
        for (auto it : nums)
        {
            if (it == 1)
            {
                num++;
            }
        }

        int ans = num;
        unordered_map<int, int>hash;
        for (int i = 0; i < num; ++i)
        {
            hash[nums[i]]++;
        }
        ans = min(ans, num - hash[1]);
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            int right = (i + num) % n;
            hash[nums[i]]--;
            hash[nums[right]]++;
            ans = min(ans, num - hash[1]);
        }
        return ans;
    }
};


//1888. 使二进制字符串字符交替的最少反转次数
//
//给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：
//
//类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
//类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。
//请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。
//
//我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。
//
//比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。


class Solution
{
public:
    int minFlips(string s)
    {
        int len = s.size();

        string s1, s2;
        for (int i = 0; i < 2 * len; ++i)
        {
            s1 += (i % 2) == 0 ? '1' : '0';
            s2 += (i % 2) == 0 ? '0' : '1';
        }
        s += s;

        int ans = len;
        int num1 = 0, num2 = 0;

        for (int i = 0; i < len; ++i)
        {
            if (s[i] != s1[i])
            {
                num1++;
            }

            if (s[i] != s2[i])
            {
                num2++;
            }
        }
        ans = min(num1, num2);
        for (int i = len; i < 2 * len; ++i)
        {
            if (s[i - len] != s1[i - len])
            {
                --num1;
            }
            if (s[i - len] != s2[i - len])
            {
                --num2;
            }

            if (s[i] != s1[i])
            {
                num1++;
            }
            if (s[i] != s2[i])
            {
                num2++;
            }

            ans = min(ans, min(num1, num2));
        }
        return ans;
    }
};


//3090. 每个字符最多出现两次的最长子字符串

class Solution
{
public:
    int maximumLengthSubstring(string s) {
        int ans = 0;
        int n = s.size();
        int left = 0, right = 0;
        unordered_map<char, int>hash;
        for (; right < n; ++right)
        {
            hash[s[right]]++;
            while (hash[s[right]] > 2)
            {
                hash[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

//1493. 删掉一个元素以后全为 1 的最长子数组
class Solution 
{
public:
    int longestSubarray(vector<int>& nums) 
    {
        int n = nums.size();
        int count = 0;
        int ans = 0;
        int left = 0, right = 0;
        for (; right < n; ++right)
        {
            if (nums[right] == 0)
            {
                count++;
            }
            while (count > 1)
            {
                if (nums[left++] == 0)
                {
                    count--;
                }
            }
            ans = max(ans, right - left);
        }
        return ans;

    }
};


//1208. 尽可能使字符串相等

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost)
    {
        int n = s.size();
        vector<int>tur(n);
        for (int i = 0; i < n; ++i)
        {
            tur[i] = abs(s[i] - t[i]);
        }
        int ans = 0;
        int mon = 0;
        int left = 0, right = 0;
        for (; right < n; ++right)
        {
            mon += tur[right];
            while (mon > maxCost)
            {
                mon -= tur[left];
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

//2730. 找到最长的半重复子字符串
class Solution 
{
public:
    int longestSemiRepetitiveSubstring(string s) {
        int n = s.size();
        vector<bool>num(n - 1);
        for (int i = 0; i < n - 1; ++i)
        {
            num[i] = s[i] == s[i + 1] ? true : false;
        }
        int ans = 0;
        int flag = 0;
        for (int left = 0, right = 0; right < n - 1; ++right)
        {
            if (num[right] == true)
            {
                flag++;
            }

            while (flag > 1)
            {
                if (num[left++] == true)
                {
                    flag--;
                }
            }
            ans = max(ans, right - left + 1);
        }
        return ans + 1;
    }
};

//904. 水果成篮

class Solution
{
public:
    int totalFruit(vector<int>& fruits)
    {
        int ans = 0;
        int n = fruits.size();
        unordered_map<int, int>hash;
        for (int left = 0, right = 0; right < n; ++right)
        {
            hash[fruits[right]]++;
            while (hash.size() > 2)
            {
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0)
                {
                    hash.erase(fruits[left]);
                }
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};


//1695. 删除子数组的最大得分
//class Solution 
//{
//public:
//    int maximumUniqueSubarray(vector<int>& nums)
//    {
//        int n = nums.size();
//        unordered_map<int, int>hash;
//        int ans = 0;
//        int num = 0;
//        for (int left = 0, right = 0; right < n; ++right)
//        {
//            hash[nums[right]]++;
//            num += nums[right];
//            while (hash[nums[right]] > 1)
//            {
//                num -= nums[left];
//                hash[nums[left]]--;
//                if (hash[nums[left]] == 0)
//                {
//                    hash.erase(nums[left]);
//
//                }
//                left++;
//            }
//            ans = max(ans, num);
//        }
//        return ans;
//
//    }
//};

//2958. 最多 K 个重复元素的最长子数组
class Solution
{
public:
    int maxSubarrayLength(vector<int>& nums, int k)
    {
        int n = nums.size();
        int ans = 0;
        unordered_map<int, int>hash;
        for (int left = 0, right = 0; right < n; ++right)
        {
            hash[nums[right]]++;
            while (hash[nums[right]] > k)
            {
                hash[nums[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;

    }
};



//2779. 数组的最大美丽值

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        k = 2 * k + 1;
        int ans = 0;
        for (int left = 0, right = 0; right < n; ++right)
        {

            while (nums[right] - nums[left] >= k)
            {
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;

    }

};

//
//2024. 考试的最大困扰度
//
//class Solution
//{
//public:
//    int maxConsecutiveAnswers(string answerKey, int k)
//    {
//        int n = answerKey.size();
//        //T
//        int ans = 0;
//        int num = 0;
//        for (int left = 0, right = 0; right < n; ++right)
//        {
//            if (answerKey[right] == 'T')
//            {
//                num++;
//            }
//            while (num > k)
//            {
//                if (answerKey[left] == 'T')
//                {
//                    num--;
//                }
//                left++;
//            }
//            ans = max(ans, right - left + 1);
//        }
//        num = 0;
//        for (int left = 0, right = 0; right < n; ++right)
//        {
//            if (answerKey[right] == 'F')
//            {
//                num++;
//            }
//            while (num > k)
//            {
//                if (answerKey[left] == 'F')
//                {
//                    num--;
//                }
//                left++;
//            }
//            ans = max(ans, right - left + 1);
//
//        }
//        return ans;
//    }
//};

//1004. 最大连续1的个数 III
//
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k)
//    {
//        int n = nums.size();
//        int ans = 0;
//        int num = 0;
//        for (int left = 0, right = 0; right < n; ++right)
//        {
//            if (nums[right] == 0)
//            {
//                num++;
//            }
//            while (num > k)
//            {
//                if (nums[left] == 0)
//                {
//                    num--;
//                }
//                left++;
//            }
//            ans = max(ans, right - left + 1);
//        }
//        return ans;
//
//    }
//};


//1658. 将 x 减到 0 的最小操作数
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x)
//    {
//        int n = nums.size();
//        int ans = -1, sum = 0;
//        int left = 0;
//        int right = 0;
//        for (auto it : nums)
//        {
//            sum += it;
//        }
//        x = sum - x;
//        if (x < 0)
//        {
//            return -1;
//        }
//        sum = 0;
//        for (; right < n; ++right)
//        {
//            sum += nums[right];
//            while (sum > x)
//            {
//                sum -= nums[left++];
//            }
//            if (sum == x)
//            {
//                ans = max(ans, right - left + 1);
//            }
//        }
//        if (ans == -1)
//        {
//            return -1;
//        }
//        else
//        {
//            return n - ans;
//        }
//
//    }
//};



//1838. 最高频元素的频数
//
//class Solution {
//public:
//    typedef long long ll;
//    int maxFrequency(vector<int>& nums, int k)
//    {
//        ll numk = 0;
//        int n = nums.size();
//        int ans = 1; 
//        sort(nums.begin(), nums.end());
//        for (int left = 0, right = 1; right < n; ++right)
//        {
//            numk += (ll)(nums[right] - nums[right - 1]) * (right - left);
//            while (numk > k)
//            {
//
//                numk -= (nums[right] - nums[left]);
//                left++;
//            }
//            ans = max(ans, right - left + 1);
//        }
//        return ans;
//    }
//};


//2516. 每种字符至少取 K 个
class Solution
{
public:
    int takeCharacters(string s, int k)
    {
        unordered_map<char, int> hash;
        int n = s.size();

        // 初始化每个字符的计数
        for (auto it : s)
        {
            hash[it]++;
        }
        if (hash['a'] < k || hash['b'] < k || hash['c'] < k)
        {
            return -1;
        }
        int ans = 0;  // 用来记录满足条件的最大窗口长度
        for (int left = 0, right = 0; right < n; ++right)
        {
            // 扩展窗口，右指针增加字符
            hash[s[right]]--;

            // 如果当前窗口有任意字符的数量小于 k，开始尝试通过左指针缩小窗口
            while (hash['a'] < k || hash['b'] < k || hash['c'] < k)
            {
                hash[s[left]]++;
                left++;  // 移动左指针
            }


            ans = max(ans, right - left + 1);

        }

        // 如果找不到有效窗口，返回 -1；否则返回最小分钟数 n - ans
        return n - ans;
    }
};

//3208. 交替组 II

class Solution
{
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k)
    {
        int n = colors.size();

        int ans = 0;
        int Pcolor = -1;
        int j = 0;
        for (int i = 0; i < n * 2; ++i)
        {
            if (Pcolor != colors[i % n])
            {
                Pcolor = colors[i % n];
            }
            else
            {
                j = i;
            }
            if (i - j + 1 == k)
            {
                ans++;
                j++;
            }

            if (j >= n)
            {
                break;
            }
        }

        return ans;
    }
};


class Solution 
{
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) 
    {

        int res = 0;
        int n = colors.size();
        int m = n + k - 1;
        int left = 0;
        int right = 1;
        //枚举起始位置
        while (left < n && right < m)
        {
            while (right < m && colors[right % n] != colors[(right - 1) % n])
            {
                ++right;
            }
            res += max(0, right - left - k + 1);
            left = right;
            right = left + 1;
        }
        return res;
    }
};

//2831. 找出最长等值子数组
class Solution
{
public:

    int longestEqualSubarray(vector<int>& nums, int k)
    {
        int n = nums.size();
        vector<vector<int>>arr(n + 1);
        for (int i = 0; i < n; ++i)
        {
            int x = nums[i];
            arr[x].push_back(i);
        }
        int ans = 0;
        for (auto pos : arr)
        {
            int left = 0;
            for (int right = 0; right < pos.size(); right++)
            {
                if (pos[right] - pos[left] - (right - left) > k)
                {
                    left++;
                }
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }
};

//双指针：三数之和
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>>ans;
        for (int i = 0; i < n - 2; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }


            int num = -nums[i];
            int left = i + 1, right = n - 1;
            if (-num + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
            if (-num + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二

            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > num)
                {
                    right--;
                }
                else if (sum == num)
                {
                    ans.push_back({ nums[i],nums[left],nums[right] });
                    left++;

                    // 跳过重复的数字
                    while (left < right && nums[left] == nums[left - 1]) 
                    {
                        left++;
                    }
                    right--;
                    while (left < right && nums[right] == nums[right + 1])
                    {
                        right--;
                    }
                }
                else
                {
                    left++;
                }
            }
        }
        return ans;
    }
};



class Solution
{
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ans, ret = 0x3f3f3f3f;
        for (int i = 0; i < n - 2; i++)
        {
            int x = nums[i];
            if (i && nums[i] == nums[i - 1])
            {
                continue;
            }

            int sum = x + nums[i + 1] + nums[i + 2];//最小的三个数之和都大于target，直接break
            if (sum > target)
            {
                if (sum - target < ret)
                {
                    ans = sum;
                }
                break;
            }
            sum = x + nums[n - 1] + nums[n - 2];//加上两个最大的都不超过target，直接continue
            if (sum < target)
            {
                if (target - sum < ret)
                {
                    ret = target - sum;
                    ans = sum;
                }
                continue;
            }

            int left = i + 1, right = n - 1;
            while (left < right)
            {
                sum = x + nums[left] + nums[right];
                if (sum == target)
                {
                    return target;
                }
                if (sum > target)
                {
                    if (sum - target < ret)
                    {
                        ret = sum - target;
                        ans = sum;
                    }
                    right--;
                }
                else
                {
                    if (target - sum < ret)
                    {
                        ret = target - sum;
                        ans = sum;
                    }
                    left++;
                }
            }
        }
        return ans;
    }
};


//11. 盛最多水的容器

class Solution//对向双指针
{
public:
    int maxArea(vector<int>& height)
    {
        int n = height.size();
        int left = 0, right = n - 1;
        int ans = 0;
        while (left < right)
        {
            if (height[left] <= height[right])
            {
                ans = max(ans, (right - left) * height[left]);
                left++;
            }
            else
            {
                ans = max(ans, (right - left) * height[right]);
                right--;
            }
        }
        return ans;
    }
};


class Solution//接雨水空间优化，相向双指针
{
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        //找到第一个递减序列
        int left = 0, right = n - 1;//空间优化
        int pre_max = 0, post_max = 0;
        int ans = 0;
        while (left < right)
        {
            pre_max = max(pre_max, height[left]);
            post_max = max(post_max, height[right]);
            if (pre_max <= post_max)
            {
                ans += (pre_max - height[left]);
                left++;
            }
            else
            {
                ans += (post_max - height[right]);
                right--;
            }
        }
        return ans;
    }
};


//209. 长度最小的子数组

class Solution
{
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int n = nums.size();
        int sum = 0;
        int left = 0, right = 0;
        int ans = n + 1;
        for (; right < n; ++right)
        {
            sum += nums[right];
            while (sum >= target)
            {
                ans = min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ans <= n ? ans : 0;
    }
};

//713. 乘积小于 K 的子数组

class Solution
{
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k)
    {
        if (k <= 1)
        {
            return 0;
        }
        int n = nums.size();
        int mul = 1;
        int left = 0, right = 0;

        int ans = 0;
        for (; right < n; ++right)
        {
            mul *= nums[right];
            while (mul >= k)
            {
                mul = mul / nums[left];
                left++;
            }

            ans += (right - left + 1);

        }
        return ans;
    }
};



//611. 有效三角形的个数
class Solution
{
public:
    int triangleNumber(vector<int>& nums)
    {
        int n = nums.size();
        int ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = n - 1; i > 1; --i)//排序之后。i就是最大的，我们只需要找两个之和大于他就行
        {
            if (nums[0] + nums[1] > nums[i])
            {
                ans += (i + 1) * i * (i - 1) / 6;
                break;
            }
            if (nums[i - 1] + nums[i - 2] <= nums[i])
            {
                continue;
            }

            for (int left = 0, right = i - 1; left < right;)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    ans += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ans;
    }
};